package leetcode;

import java.util.LinkedList;

public class LC1926 {

    public static int nearestExit(char[][] maze, int[] entrance) {
        int m = maze.length;
        int n = maze[0].length;
        int[] dx = {0,0,-1,1};
        int[] dy = {1,-1,0,0};
        boolean[][] vist = new boolean[m][n];

        LinkedList<int[]> queue = new LinkedList<>();
        queue.push(entrance);
        vist[entrance[0]][entrance[1]] = true;
        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            step ++;
            for (int i = 0; i < size; i++) {
                int[] pos = queue.removeFirst();
                for (int j = 0; j < dx.length; j++) {
                    int px = pos[0] + dx[j];
                    int py = pos[1] + dy[j];
                    if (px >= 0 && px < m && py >=0 && py < n && maze[px][py] == '.'
                            && !vist[px][py]) {
                        if (px == 0 || py == 0 || px == m -1 || py == n - 1)
                            return step ;
                        queue.addLast(new int[]{px, py});
                        vist[px][py] = true;
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println("asaaw" + 's');
    }
}
